package donggui;

import java.util.Map;

/*
* 编辑距离leetcode72题
* */
public class item72 {
    int [][]memo;
    public int minDistance(String word1, String word2) {
        int m = word1.length();
        int n = word2.length();
        memo = new int[m][n];
//        针对字符串的动态规划一般都从后往前缩小规模
        return dp(word1,m-1,word2,n-1);
    }

    private int dp(String s1, int i, String s2, int j) {
        if(i==-1) return j+1; //这个地方理解不是很透彻，但是大概意思就是如果母串走完了，就需要把子串上的删除才能完全匹配
        if(j==-1) return i+1;
        if(memo[i][j]!=0) return memo[i][j];
        if(s1.charAt(i)==s2.charAt(j))
           memo[i][j] =  dp(s1,i-1,s2,j-1);
        else
        memo[i][j]= min(
                 dp(s1,i,s2,j-1)+1,//增加一个字符
                    dp(s1,i-1,s2,j)+1,//删除一个字符
                    dp(s1,i-1,s2,j-1)+1 //修改一个字符
            );
        return memo[i][j];
    }

    int min(int a, int b, int c) {
        return Math.min(a, Math.min(b, c));
    }
}
